Field
Various features relate to cryptography, and more particularly to methods and apparatuses for implementing Substitution-boxes.
Background
In cryptography, a Substitution-box (S-box) is a basic component of symmetric key algorithms that perform substitution. In block ciphers, they are typically used to obscure the relationship between a key and cipher-text, and thus demonstrate Shannon's property of confusion. The S-box represents a complex function that receives n input bits and generates m output bits, such that the output has certain cryptographically useful properties. These properties include high non-linearity and balance, high algebraic degree, strict avalanche criterion satisfaction, and other properties. Such functions are hard to compute and are often represented as lookup tables, such as in the Data Encryption Standard (DES) and Advanced Encryption Standard (AES). For example, in AES an 8-bit input is replaced by the 8-bit value selected from an S-box. In some cases, n may equal m so that the input and output to the S-box have the same bit lengths.
If n is large, the lookup tables described above (or equivalently a network of gates for a hardware implementation) can quickly become unwieldy. On the other hand, a small n is by definition limited in nonlinearity and algebraic degree. Therefore, an S-box having a large number of input bits that is also able to be efficiently implemented in hardware or software is desirable.
A Hidden Weighted Bit Function (HWBF) may be viewed as an n-bit to 1-bit S-box that enjoys some of the desirable cryptographic properties described above, such as balance and algebraic complexity. For example, if x is an n-bit input, with xi being the i-th (1<=i<=n) most significant bit of x, then the output W of the HWBF is defined as:
W(x)=0 if x=0,
W(x)=xk where k is the Hamming Weight of x, otherwise.
FIG. 1 illustrates a schematic block diagram of an n-bit to n-bit HWBF based S-box 100 found in the prior art that may be easily implemented in hardware. A binary input value x (e.g., 110101) is input into a rotate function 102. The rotate function 102 performs a bitwise rotation left on the input x by a number of bits equal to the Hamming Weight of the input. Thus, if the binary input x equals 110101, the output z of the rotate function 102 is equal to 011101 since the Hamming Weight is equal to four (4).
FIG. 2 illustrates a table 200 depicting the relationship between the HWBF based S-box output z and the HWBF W(x). Referring to FIGS. 1 and 2, it may be shown that the least significant bit of the output z (e.g., 1) is equal to the HWBF W(x) (defined above) of the input value x. It may also be observed that the second least significant bit (e.g., 0) represents the output of the HWBF W(x) if the input value x to the HWBF had undergone a single bit bitwise rotation right (denoted by W(x<<1)). The third least significant bit represents the output of the HWBF W(x) if the input value x to the HWBF had undergone a two bit bitwise rotation right (denoted by W(x<<2)), and so on.
Thus, the output value z has the same number of bits as the input value x where each bit represents a different HWBF W(x) output computed in parallel. The bits of the output value z still retain some of the beneficial cryptographic properties described above with respect to HWBFs. Unfortunately, the S-box 100 also has undesirable properties. For example, one such undesirable property is that the output z will have the same Hamming weight as the input x, which can often simplify cryptanalysis, particularly when the input x is of low Hamming Weight. It would be desirable to increase the security of the S-box 100 to make it more resistant to cryptographic attacks (cryptanalysis).
Thus, there is a need for improved S-box algorithms, methods, and apparatuses that are more robust against cryptographic attacks.